class Solution:
    """
    定义两个指针： pre 和 cur ；pre 在前 cur 在后。
    每次让 pre 的 next 指向 cur ，实现一次局部反转
    局部反转完成之后，pre 和 cur 同时往前移动一个位置
    循环上述过程，直至 pre 到达链表尾部
    """

    def reverseList1(self, head: ListNode) -> ListNode:  # 双指针
        pre = head
        cur = None
        while pre != None:
            tmp = pre.next
            pre.next = cur
            cur = pre
            pre = tmp
        return cur

    """
    使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
    此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
    同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
    当递归函数全部出栈后，链表反转完成。
    """

    def reverseList2(self, head: ListNode) -> ListNode:  # 递归
        if head == None or head.next == None:
            return head
        tmp = self.reverseList2(head.next)
        head.next.next = head
        head.next = None
        return tmp

    """
    原链表的头结点就是反转之后链表的尾结点，使用 head 标记 .
    定义指针 cur，初始化为 head .
    每次都让 head 下一个结点的 next 指向 cur ，实现一次局部反转
    局部反转完成之后，cur 和 head 的 next 指针同时往前移动一个位置
    循环上述过程，直至 cur 到达链表的最后一个结点 .
    """

    def reverseList3(self, head: ListNode) -> ListNode:
        if head == None:
            return None
        cur = head
        while head.next != None:
            tmp = head.next.next
            head.next.next = cur
            cur = head.next
            head.next = tmp
        return cur
